package com.yusong.algorithm;


import com.yusong.algorithm.data.DataConstants;

/**
 * 希尔排序
 * 插入排序的优化
 */
public class ShellSort extends AbstractSort {


    @Override
    public void sort(Comparable[] a) {
        int length = a.length;
        int h = Math.round(length / 3) + 1;
        while (h >= 1) {
            for (int i = 0; i < h; i++) {
                //插入排序
                int n = 1;
                while ((i + n * h) < length) {
                    if (!less(a[i + n * h], a[i + n * h - h])) {
                        n++;
                        continue;
                    }
                    exchange(a, i + n * h, i + n * h - h);
                }
            }
            h--;
        }
    }


    public static void main(String[] args) {
        ShellSort shellSort = new ShellSort();
        shellSort.sort(DataConstants.NUM_SIMPLE);
        show(DataConstants.NUM_SIMPLE);
    }
}


/**
 * 希尔排序说明
 * 权衡数组的有序性和规模
 * 优化插入排序相邻移动的弊端，H很大的时候可以大范围移动。
 * 算法：希尔排序的思想是使数组中任意 间隔为h 的元素都是有序的。
 * 可以看到，希尔排序比插入排序和选择排序要快得多，并且数组越大，优势越大。
 */